class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        dp[0] = 0;
        for (int i=1; i<=amount; i++){
            int min_ = Integer.MAX_VALUE;
            for (int coin : coins){
                if (i >= coin && dp[i-coin] >= 0) {
                    min_ = Math.min(min_, dp[i-coin]+1);
                }
            }
            min_ = min_== Integer.MAX_VALUE?-1:min_;
            dp[i] = min_;
        }
        return dp[amount];
    }
}